package 算法.排序;

public class 快速 {
    public static void main(String[] args) {
        int[] arr={16,5,9,12, 21,18, 32,23,37,26,45,34, 50,48,61,52,73,66};

        quickSort(arr,0,arr.length-1);
        printArr(arr);
    }
    public static void quickSort(int[] arr,int i,int j){
        int start=i;
        int end=j;

        // 递归出口
        if(start>end){
            return;
        }

        // 确定基准数
        int baseNumber=arr[start];

        while (start!=end){
            while(true){
                if (end<=start || arr[end]<baseNumber){
                    break;
                }
                end--;
            }
            while(true){
                if(end<=start || arr[start]>baseNumber){
                    break;
                }
                start++;
            }
            // 交换Arr【start】和arr【end】
            swap(arr ,start,end);
        }
        // 交换基准数和第一个数
        swap(arr,i,start);
        quickSort(arr,i,start-1);
        quickSort(arr,start+1,j);

    }
    private static void swap(int[] arr, int a, int b) {
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
